package com.company;

public class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode listNode = new ListNode();
        for (ListNode l1 : lists){
            listNode = mergeTwoLists(listNode,l1);
        }
        return listNode;
    }

    public static void main(String[] args) {
        Solution23 solution23 = new Solution23();

    }

    public ListNode mergeTwoLists(ListNode l1,ListNode l2) {
        if (l1 == null && l2 != null){
            return l2;
        }else if(l1!= null && l2 == null){
            return l1;
        }else if(l1== null && l2 == null){
            return null;
        }else{
            ListNode res = new ListNode(Math.min(l1.val,l2.val));
            ListNode l = res;
            while (l1!=null&&l2!=null){
                if (l1.val<=l2.val){
                    ListNode tmp = new ListNode(l1.val,l1.next);

                    l.next = tmp;
                    l1 = l1.next;
                    l = tmp;
                }else {
                    ListNode tmp = new ListNode(l2.val,l2.next);
                    l.next = tmp;
                    l2 = l2.next;
                    l = tmp;
                }
            }
            if (l1 == null){
                l.next = l2;
            }
            if (l2 == null){
                l.next = l1;
            }
            return res.next;
        }
    }
}
